5000년전 데니스 리치경이 쑥과 마늘만 먹으며 씨언어를 개발한 이래로, 비트 개수 세기 같은 기초적인 문제는 연습 문제류로 등장하곤 했으나.. 간만에 인터넷 검색해보니 나오는 글들을 5000년째 정직한 루프를 돌고 있다. 뭐, 알고리즘 수업을 들은 적이 없어서 그렇지 이런저런 트릭이야 많을 것이다.
말하자면 정직한 루프란 이렇다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, j;
unsigned int k;
long count = 0;
for (i = 0; i < 100000000; i++) {
k = rand();
for (j = 0; j < 32; j++) {
count += k >> j & 0x1;
}
}
printf("%ld\n", count);
}이 얼마나 SCV 부려먹는 이야기인가. 우리는 천재니까 8비트씩 테이블로 바꿔서 다시 만들자.
#include <stdio.h>
#include <stdlib.h>
char bit_count[0xFF + 1] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };
int main()
{
int i, j;
unsigned int k;
long count = 0;
for (i = 0; i < 100000000; i++) {
k = rand();
for (j = 0; j < 8; j++) {
count += bit_count[k >> (8 * j) & 0xff];
}
}
printf("%ld\n", count);
}해보니까 3.4초대 0.8초 나온다. 즉슨 4배 이상 빠르다. 뭐 메모리도 널널한데 16비트씩 비교해도 된다. 16비트를 테이블로 갖고 있으려면 64K를 소모한다. 64K는 동네 초딩한테 가서 달라고 해도 준다.
그런데, 세상도 좋아졌는데 그냥 sse를 써봅시다.
#include <stdio.h>
#include <stdlib.h>
#include <immintrin.h>
int main()
{
int i, j;
int k;
long count = 0;
for (i = 0; i < 100000000; i++) {
k = rand();
count += __builtin_popcount(k);
}
printf("%ld\n", count);
}
그러니까 0.8초에서 0.7초로 단축되긴 합니다. 아마도 rand가 시간 다 먹는 듯...
여기서 SIMD(AVX2)로 더욱 쪼여볼 순 있겠습니다. 그런데 왜 이 짓거리를? 비밀..